#leetcode题目238：除自身以外数组的乘积
#难度：中等

#方法：前缀和
#看似简单，但是在有0的情况下是失效的。
#注意：请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
from typing import List

class Solution:
#方法：左右乘积列表
    #leetcode官方题解，
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        
        # L 和 R 分别表示左右两侧的乘积列表
        L, R, answer = [0]*length, [0]*length, [0]*length
        
        # L[i] 为索引 i 左侧所有元素的乘积
        # 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
        L[0] = 1
        for i in range(1, length):
            L[i] = nums[i - 1] * L[i - 1]
        
        # R[i] 为索引 i 右侧所有元素的乘积
        # 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
        R[length - 1] = 1
        for i in reversed(range(length - 1)):
            R[i] = nums[i + 1] * R[i + 1]

        # 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        for i in range(length):
            answer[i] = L[i] * R[i]
        
        return answer

    #解法来自第三个视频，由java转成python而来。
    #TODO



#测试数据
nums = [1,2,3,4]
#预期输出：[24,12,8,6]

solution = Solution()
print(solution.productExceptSelf(nums))

nums = [-1,1,0,-3,3]
#预期输出：[0,0,9,0,0]

solution = Solution()
print(solution.productExceptSelf(nums))



